HW#5 --- last modified February 17 2019 19:23:37..

Solution set.

Due date: May 16

Files to be submitted:
  Hw5.zip

Purpose: To learn more about Turing and Karp reductions, completeness, and undecidability.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO10 -- State in precise mathematical terms what is meant by undecidability of the Halting Problem, and be able to show the undecidability of simple extensions of the Halting Problem, using the reduction technique.

Specification:

Please do the following problems and submit them in a PDF or html file in Hw5.zip:

1. (a) Show `A_{LBA}` is complete for PSPACE with respect to Karp reductions. (b) Show `A_{clocked TM}` is complete for NEXP with respect to exponential time reductions.
2. Show `A_{TM}` is r.e. complete under Karp reductions. For 1 bonus point, show there is an r.e. language which is complete for r.e. under Turing Reductions but which is not complete for r.e. under Karp reductions.
3. Do problem 5.21 in the book.
4. Consider the language
   `L = { \langle M rangle | \mbox{ for each } n ge 0, mbox{ M accepts half of the strings rounded up of length } n}`
   Use Rice's Theorem to show this language is undecidable.
5. Give an upper bound as a function of `n` of `K(2^{n})` by explicitly building a machine and finding an input as small as possible to calculate `2^{n}`.

Point Breakdown